12.6 KB · ⇊ 4 parts · ⤓ Micron 12.6 KB · ⤓ HTML 54.1 KB

top

LOOP-Programme sind Programme in der Programmiersprache LOOP, einer stark eingeschränkten, modellhaften Sprache, die nur die Formulierung von Additionen, Wertzuweisungen und endlich oft durchlaufende Schleifen erlaubt. LOOP-Programme spielen in der Theoretischen Informatik eine Rolle, insbesondere im Zusammenhang mit Berechenbarkeit. Eine Funktion heißt LOOP-berechenbar, wenn sie sich als LOOP-Programm formulieren lässt. Die Menge aller LOOP-Programme wird mit L O O P {\displaystyle {\mathit {LOOP}}} bezeichnet.

• Eigenschaften

• Formale Definition

• Syntax

• Semantik

• Beispielprogramme

• Addition

• Multiplikation

• IF THEN ELSE

• Simulation von LOOP-Programmen durch WHILE-Programm

• Siehe auch

• Einzelnachweise

• Literatur

Aufgrund ihrer Definition terminieren LOOP-Programme für alle Eingaben und definieren daher totale Funktionencite-ref-1[1]. Damit stehen sie im Kontrast zu GOTO-Programmen und WHILE-Programmen, bei denen eine Terminierung des Programms nicht garantiert ist.

Die Menge der durch LOOP-Programme berechenbaren Funktionen ist eine echte Untermenge der berechenbaren totalen Funktionen (und damit auch eine Untermenge der durch WHILE- bzw. GOTO-Programme berechenbaren Funktionen)cite-ref-0-2-0[2]. Ein Beispiel für eine berechenbare, aber nicht LOOP-berechenbare totale Funktion ist die Ackermann-Funktioncite-ref-3[3].

Die Menge der LOOP-berechenbaren Funktionen entspricht der Menge der primitiv-rekursiven Funktionencite-ref-4[4].

LOOP-Programme bestehen aus den Symbolen LOOP, DO, END, :=, +, - und ; sowie einer beliebigen Anzahl von Variablen und Konstanten. LOOP-Programme haben folgende Syntax in modifizierter Backus-Naur-Form:

P := x i := x j + c | x i := x j − − c | P ; P | L O O P x i D O P E N D {\displaystyle {\begin{array}{lrl}P&:=&x_{i}:=x_{j}+c\\&|&x_{i}:=x_{j}-c\\&|&P;P\\&|&\mathrm {LOOP} \,x_{i}\,\mathrm {DO} \,P\,\mathrm {END} \end{array}}}

Hierbei sind V a r := { x 0 , x 1 , . . . } {\displaystyle {\mathit {Var}}:=\{x_{0},x_{1},...\}} Variablennamen und c ∈ ∈ N {\displaystyle c\in \mathbb {N} } Konstanten.

Ein Ausdruck der Form

bedeutet die Zuweisung des um c {\displaystyle c} erhöhten Wertes der Variablen x 1 {\displaystyle x_{1}} an die Variable x 0 {\displaystyle x_{0}} . Dabei ist für c {\displaystyle c} der Wert Null zulässig, so dass sich auch die direkte Zuweisung des Wertes einer Variablen an eine andere Variable mit diesem syntaktischen Konstrukt formulieren lässt:

Ein Ausdruck der Form

bedeutet die Zuweisung des um c {\displaystyle c} verminderten Wertes der Variablen x 1 {\displaystyle x_{1}} an die Variable x 0 {\displaystyle x_{0}} . Bei der Ausführung von Zuweisungen werden negative Werte implizit durch Nullen ersetzt.

Variablen dürfen in Zuweisungsausdrücken gleichzeitig auf der linken und auf der rechten Seite des Symbols := erscheinen. Ein Ausdruck der Form

erhöht beispielsweise den Wert der Variablen x {\displaystyle x} um c {\displaystyle c} .

Die in einem LOOP-Programm verwendeten Variablen werden vor Beginn des Programmablaufs mit vorgegebenen Initialwerten vorbelegt.

Ein Ausdruck der Form

bedeutet die Hintereinanderausführung der Teilprogramme P 1 {\displaystyle P_{1}} und P 2 {\displaystyle P_{2}} in dieser Reihenfolge. Ein Ausdruck der Form

bedeutet die x {\displaystyle x} -fache Ausführung des Teilprogramms P {\displaystyle P} , wobei x {\displaystyle x} den Wert am Beginn der Abarbeitung darstellt. (Auch wenn x {\displaystyle x} durch die Ausführung von P {\displaystyle P} verändert wird, wird P {\displaystyle P} nur so oft ausgeführt, wie x {\displaystyle x} am Anfang war.) Hat x {\displaystyle x} dabei den Wert Null, so wird das Teilprogramm P {\displaystyle P} innerhalb des LOOP-Ausdrucks überhaupt nicht ausgeführt. Dieser Umstand erlaubt die Formulierung von Verzweigungen in LOOP-Programmen durch die bedingte Ausführung von Teilprogrammen in Abhängigkeit vom Wert einer Variablen.

Das folgende LOOP-Programm weist der Variablen x 0 {\displaystyle x_{0}} die Summe der Werte der Variablen x 1 {\displaystyle x_{1}} und x 2 {\displaystyle x_{2}} zu.

Dabei bekommt zunächst x 0 {\displaystyle x_{0}} den aktuellen Wert von x 1 {\displaystyle x_{1}} zugewiesen und wird dann um den Wert von x 2 {\displaystyle x_{2}} inkrementiert.

Dieses Programm lässt sich wie ein Unterprogramm in anderen LOOP-Programmen verwenden. Solche Verwendungen werden durch eine einfache Erweiterung der ursprünglichen LOOP-Syntax in der Form

beschrieben.

Dabei gilt zu beachten, dass LOOP-Programme keine Unterprogramme aufrufen könnencite-ref-5[5], sondern diese Unterprogramme inlined und somit ein Teil des Hauptprogramms werdencite-ref-6[6]cite-ref-0-2-1[2]. Andernfalls bestände die Möglichkeit einer zirkulären Abhängigkeit und damit einhergehend der Verlust der endlichen Laufzeit von LOOP-Programmen.

Das folgende LOOP-Programm erhöht den Wert der Variablen x 0 {\displaystyle x_{0}} um den Wert des Produktes der Werte der Variablen x 1 {\displaystyle x_{1}} und x 2 {\displaystyle x_{2}} .

Das Programm benutzt dabei das im ersten Beispiel definierte Unterprogramm der Addition. Die ausgeführte Multiplikation wird dabei durch das x 1 {\displaystyle x_{1}} -fache Addieren des Wertes von x 2 {\displaystyle x_{2}} zum Wert von x 0 {\displaystyle x_{0}} realisiert.

Durch Einsetzen des LOOP-Programms für die Addition erhält man das äquivalente Programm in der ursprünglichen LOOP-Syntax.

Das folgende LOOP-Programm simuliert eine „if x1 > c then P1 else P2“-Anweisung, wobei x1 eine Variable, c eine Konstante und P1, P2 beliebige LOOP-Programme sind. In dem Programm werden drei neue Variablen xn1, xn2, xn3 verwendet.

Das folgende LOOP-Programm simuliert eine „if x1 = c then P1 else P2“-Anweisung, wobei x1 eine Variable, c eine Konstante und P1, P2 beliebige LOOP-Programme sind. In dem Programm werden vier neue Variablen xn1, xn2, xn3, xn4 verwendet.

Ein jedes LOOP-Programm

kann durch das folgende WHILE-Programm simuliert werden

• µ-Rekursion

• WHILE-Programm

• GOTO-Programm

cite-note-11. ↑ Uwe Schöning: Theoretische Informatik- kurz gefasst. 5. Auflage. Spektrum Akademischer Verlag, Heidelberg 2008, ISBN 978-3-8274-1824-1, S. 93.

cite-note-0-22. ↑ Uwe Schöning: Theoretische Informatik- kurz gefasst. 5. Auflage. Spektrum Akademischer Verlag, Heidelberg 2008, ISBN 978-3-8274-1824-1, S. 93,94.

cite-note-33. ↑ Uwe Schöning: Theoretische Informatik- kurz gefasst. 5. Auflage. Spektrum Akademischer Verlag, Heidelberg 2008, ISBN 978-3-8274-1824-1, S. 94,112.

cite-note-44. ↑ Uwe Schöning: Theoretische Informatik- kurz gefasst. 5. Auflage. Spektrum Akademischer Verlag, Heidelberg 2008, ISBN 978-3-8274-1824-1, S. 105.

cite-note-55. ↑ Till Tantau: Vorlesungsskript Theoretische Informatik. In: Institut für Theoretische Informatik - Universität zu Lübeck. 12. Februar 2010, S. 154–156, abgerufen am 23. Januar 2019: „Unterprogramme sind nicht erlaubt.“

cite-note-66. ↑ Uwe Schöning: Theoretische Informatik - kurz gefasst. 5. Auflage. Spektrum Akademisch Verlag, S. 102: „Die Funktion g (...) kann formal durch eine entsprechende Einsetzung definiert werden (...)“

• Uwe Schöning: Theoretische Informatik - kurzgefasst. 4. Auflage. Spektrum Akademischer Verlag, 2001, ISBN 3-8274-1099-1.